1. Field of the Invention
This invention relates to facsimile signal redundancy reduction coding and transmission, and more particularly to a method and apparatus for sequential edge difference coding and transmission of a binary signal, in which method and apparatus picture is scanned so as to be resolved into picture elements (pels) of a first level (for example, a black level) and a second level (for example, a white level), and in which the edge states between the first and second levels between the current line to be coded and the line immediately preceding it are coded and transmitted.
2. Description of the Prior Art
In recent years, facsimile has become known as a simple method of transmitting documents, and has been put into wide use and developed. However, the amount of facsimile signal obtained by scanning an original document is enormous. For example, in the case of sampling a document of JIS-A4 (210.times.297 mm) with a sampling density of 8 pels/mm both in main- and sub-scanning directions and producing a binary representation, the amount of facsimile signal reaches about 4.times.10.sup.6 bits. Therefore, much time is needed for directly transmitting the signals and a large capacity memory is required for storing them.
Then, various redundancy reduction coding schemes have been proposed for highly efficient transmission of facsimile signals. These schemes all take advantage of the redundancy within the facsimile signal and reduce the number of bits to be transmitted or stored by the technique of redundancy reduction coding without impairment of picture quality.
The fundamental idea of the redundancy reduction coding scheme is to identify a signal train having redundancy as a sequence of successive states, and to represent each of the states by variable length codes in accordance with the frequency of occurrence of each state.
The most excellent one of the conventional coding schemes is the two-dimensional sequential coding scheme which performs coding by sequentially making use of correlation between adjacent scan lines.
For the two-dimensional sequential coding scheme, refer to the following literatures:
(i) The Institute of Television Engineers of Japan, The Society for the Study of Picture Transmission, research material 17-6 (1975-10), Yamada, Togashi and Yuki "Modified Predictive Differential Quantizing (PDQ) for Facsimile Signals." PA1 (ii) The Institute of Electronics and Communication Engineers of Japan, Department of Communication, General Meeting in 1976, manuscript S5-5 (1976), Yamada and Kawade, "On a Predictive Differential Quantizing in Patterns for Facsimile Signals." PA1 (iii) The Institute of Electronics and Communication Engineers of Japan, the Society for the Study of Communication System, research material CS74-115 (1974-11), Wakahara (Kokusai Denshin Denwa K.K.), "Relative Address Coding Scheme." PA1 (iv) British Pat. No. 1,307,777 Specification PA1 (v) U.S. Pat. No. 3,991,267 Specification PA1 (vi) Japanese Patent Laid-Open No. 1851/1976 Gazette PA1 (vii) French Patent No. 1,548,366 Specification PA1 (vii) ICC 1969 (11-21.about.11.about.28) V. M. Tyler (EG & G) "Two Handcopy Terminal for PCM Communication of Meteorological Products." PA1 (ix) Picture Bandwidth Compression. Goden, Breach & C. G. Beaudette "An Efficient Facsimile System for Weather Graphics" PA1 (x) Picture Bandwidth Compression. Goden, Breach & T. S. Huang "Run-Length Coding and its Extensions".
However, the above said methods have defects in that the coding algorithm is complicated, that a high compression ratio cannot be obtained, that even if a high compression ratio can be obtained in connection with either one of simple and complicated documents, a sufficiently high compression ratio cannot be obtained in connection with the other, and that implementation becomes complicated. Accordingly, there is still room for improvements.
The contents of above said literatures (iv), (v), (vi), (viii), (ix) and (x) relate to the PDQ scheme disclosed in British Pat. No 1,307,777.
Briefly stated, the PDQ scheme is as follows: When coding a signal of the current line while sequentially comparing signals of two adjacent scan lines, a difference .DELTA.I in the black run starting position between corresponding portions on both scan lines and a difference .DELTA.II in the black run length between the abovesaid corresponding portions are measured, and the two functions .DELTA.I and .DELTA.II are coded in a pair. Accordingly, especially in the case of a complicated document, the absolute value of the function .DELTA.II becomes large so as to lessen the effect of redundancy reduction, so that a high compression ratio cannot be obtained. Further, since both functions .DELTA.I and .DELTA.II are coded in a pair, implementation becomes complicated.
Next, the method set forth in the abovesaid French Pat. No. 1,548,366 is such that, in connection with the pel arrangement that the positions of pels on the preceding and current lines adjacent to each other are shifted by 1/2 pel relative to each other, black run lengths on the both lines are classified and coded. That is, the pel arrangement is interleaved and notice is taken of a pair of black runs, and the difference between the leading point and the lagging point of the overlapping black runs are coded in a pair and, at the same time, an address is coded for coding of the leading point of the run length. Accordingly, coding in a pair makes implementation complicated and, since address coding is not efficient, a high compression ratio cannot be obtained in the case of a complicated document.
Next, the relative address coding scheme proposed in the abovesaid literature (iii) is such that a new transition point is coded with the relative address from the basic point which is the nearest one of the adjoining transition points already coded. This is based on the idea that images on the document are examined upwards, so that if the document is complicated, there is no correlation between the new transition point, and the basic point and the relative distance becomes large, and the effect of redundancy reduction is lessened.
Further, the technique of predictive differential quantizing in patterns proposed by the present inventors in the abovesaid literature (ii) amounts to classifying the way of connection of black portions on two adjacent scan lines into five kinds and coding them. This scheme is more satisfactory than the abovesaid relative address coding scheme in which images on the document are examined downwards. Further, this has been reformed from the abovesaid PDQ scheme but implementation is relatively complicated.